package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/10/12 9:33
 */
public class LC29两数相除 {

    public static int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 1) return dividend;
        if (divisor == -1) {
            if (dividend > Integer.MIN_VALUE) return -dividend;
            return Integer.MAX_VALUE;
        }
        int flag = 1;
        if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
            flag = -1;
        }
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        return flag == 1 ? recursion(dividend, divisor) : -recursion(dividend, divisor);
    }

    public static void main(String[] args) {
        System.out.println(divide(13, 2));
    }

    private static int recursion(int dividend, int divisor) {
        if (dividend > divisor) return 0;
        int count = 1, temp = divisor;
        // 如果对temp翻倍，就可能越界， 所以算divided减半。不能用 <= 号 由于 divided>>1可能牺牲精度，本来是 tem<<1不满足的情况变满足
        while ((dividend >> 1) < temp) {
            count <<= 1;
            temp <<= 1;
        }
        return count + recursion(dividend - temp, divisor);
    }
}
